package www.study.com;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class code22 {
    public static void main(String[] args) {

    }


     public class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     }

    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            //主要lists数组中，可能第一个元素为null，但是之后的元素不为null，所以，不能以第一个是否为空作为退出条件，如③的推出逻辑是不对的[[],[1]]
            if(lists == null || lists.length == 0){ //lists[0] == null   ③
                return null;
            }
            Queue<ListNode> queue = new PriorityQueue<ListNode>(new Comparator<ListNode>(){
                public int compare(ListNode node1,ListNode node2){
                    return Integer.compare(node1.val,node2.val);
                }
            });
            for(ListNode node:lists){
                if(node != null)
                    queue.add(node);
            }
            ListNode now = null;
            ListNode head = null;
            while(!queue.isEmpty()){
                ListNode cur = queue.poll();
                if(now == null){
                    now = cur;
                    head = now;
                }else{
                    now.next = cur;
                    now = now.next;
                }
                if(cur.next != null){
                    queue.add(cur.next);
                }
            }
            return head;
            //return func(lists,0,lists.length - 1);
        }
        public ListNode func(ListNode[] lists,int lef,int rig){
            if(lef <= rig){
                int mid = (lef + rig) >> 1;
                ListNode lefRes = func(lists,lef,mid);
                ListNode rigRes = func(lists,mid + 1,rig);
                return merge(lefRes,rigRes);
            }
            return null;
        }
        //方式一：归并排序的思路
        public ListNode merge(ListNode list1, ListNode list2){
            if(list1 == list2) return list1;
            ListNode head = null;
            ListNode res = null;
            while(list1 != null || list2 != null){
                ListNode cur = null;
                if(list1 != null && list1.val <= list2.val){
                    cur = list1;
                    list1 = list1.next;
                }else{
                    cur = list2;
                    list2 = list2.next;
                }
                if(res == null){
                    res = cur;
                    head = cur;
                }else{
                    res.next = cur;
                    res = res.next;
                }
            }
            return head;
        }
    }
}
